#include<iostream>
#include<stack>
#include<vector>
using namespace std;
//LeetCode 739.每日温度
vector<int> dailyTemperatures(vector<int>& temperatures) {
    //用于存储栈中元素的下标，并且为单调栈
    stack<int> s;
    vector<int> result(temperatures.size(), 0);
    s.push(0);
    for(int i=1;i<temperatures.size();i++)
    {
        while(!s.empty()&&temperatures[s.top()]<temperatures[i])
        {
            result[s.top()] = i-s.top();
            s.pop();
        }
        s.push(i);
    }
    return result;
}
int main()
{
    vector<int> t = {73, 74, 75, 71, 69, 72, 76, 73};
    vector<int> result = dailyTemperatures(t);
    for (int i = 0; i < result.size(); ++i) {
        cout << result[i] << " ";
    }
    return 0;
}